package datastructure.book.tujiesuanfa.find._2_more;

import org.junit.jupiter.api.Test;

public class Solution {

    @Test
    public void testCountTarget(){
        System.out.println(countTarget(new int[]{2}, 2));
    }

    /**
     * 非严格递增整数数组 scores，请返回目标成绩 target 的出现次数。数组中不存在target返回0
     * 非严格递增，即相邻元素可能相等的递增
     * 例：1,2,3,3,4，4，5  其中 3出现2次
     * 找到目标数，然后左右扩展找到出现的总次数，在极端情况下时间复杂度为O(n)
     * 例如：1,1,1,1,1,1  目标数为：1
     * 使用O(log n)的时间复杂度实现
     */
    public int countTarget(int[] scores, int target) {
        if (scores == null || scores.length == 0) {
            return 0;
        }
        int i = tarRightIndex(scores, target,true);
        if (i == -1) {
            return 0;
        }
        int j = tarRightIndex(scores,target-1,false);
        return i-j;
    }
    private int tarRightIndex(int[] scores, int target,boolean needFind){
        int i = 0;
        int j = scores.length-1;
        boolean find = false;
        while (i <= j) {
            int mid = (i+j)/2;
            if (scores[mid] < target) {
                i = mid + 1;
            } else if (scores[mid] > target) {
                j = mid - 1;
            } else {
                i = mid + 1;
                find = true;
            }
        }
        if (needFind) {
            return find ? i : -1;
        } else {
            return i;
        }
    }

    /**
     * 找到数组中缺少的自然数，仅缺少一个
     * 例：
     * [0,1,2,3,5]  缺少  4
     * [0,1,3,4,5]  缺少  2
     */
    public int takeAttendance(int[] records) {
        if (records == null || records.length == 0) {
            return 0;
        }
        int i = 0;
        int j = records.length-1;
        while (i <= j) {
            int mid = (i+j)/2;
            if (records[mid] == mid) {
                i = mid + 1;
            } else {
                j = mid - 1;
            }
        }
        return i;
    }

    /**
     * 二维数组，每行递增，每列递增，查找是否有目标数
     * 例：是否有8，返回true
     * 1, 4, 7, 11,15
     * 2, 4, 8, 12,19
     * 3, 5, 9, 16,22
     * 10,11,14,17,24
     * 18,19,23,26,30
     */
    public boolean findTargetIn2DPlants(int[][] plants, int target) {
        if (plants == null || plants.length == 0 || plants[0].length == 0) {
            return false;
        }
        int row = plants.length-1;
        int col = 0;
        while (col < plants[0].length && row >= 0) {
            if (plants[row][col] > target) {
                row--;
            } else if (plants[row][col] < target) {
                do {
                    col++;
                }
                while (col < plants[0].length && plants[row][col] < target);
            } else {
                return true;
            }
        }
        return false;
    }

    /**
     * 已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。
     * 例如，原数组 nums = [0,1,4,4,5,6,7] 在变化后可能得到：
     * 若旋转 4 次，则可以得到 [4,5,6,7,0,1,4]
     * 若旋转 7 次，则可以得到 [0,1,4,4,5,6,7]
     * 注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。
     * 给你一个可能存在 重复 元素值的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。
     * 请你找出并返回数组中的 最小元素 。
     */
    public int inventoryManagement(int[] stock) {
        if (stock == null || stock.length == 0) {
            return 0;
        }
        if (stock[0] < stock[stock.length - 1]) {
            return stock[0];
        }
        int i = 0;
        int j = stock.length-1;
        while (i < j) {
            int mid = (i+j)/2;
            if (stock[mid] > stock[j]) {
                i = mid+1;
            } else if (stock[mid] < stock[j]) {
                j = mid;
            } else {
                j = j-1;
            }
        }
        return stock[i];
    }
}
